1.后缀数组SA(快排版)
const int N = 3e6+7;
int lcp[N],sa[N];
namespace SA
{
int rank[N],tmp[N];
int n,k;
bool sa_cmp(int i,int j)
{
if(rank[i] != rank[j]) return rank[i] < rank[j];
else
{
int ri = i + k <= n ? rank[i + k] : -1;
int rj = j + k <= n ? rank[j + k] : -1;
return ri < rj;
}
}
void build_sa(string& s)
{
n = s.size();
for(int i = 0;i <= n;++i)
{
sa[i] = i;
rank[i] = i < n ? s[i] : -1;
}
for(k = 1;k <= n;k *= 2)
{
sort(sa,sa + 1 + n,sa_cmp);
tmp[sa[0]] = 0;
for(int i = 1;i <= n;++i) tmp[sa[i]] = tmp[sa[i - 1]] + sa_cmp(sa[i - 1],sa[i]);
for(int i = 0;i <= n;++i) rank[i] = tmp[i];
}
}
bool contain(string& s,string& T)
{
int l = 0,r = s.size();
while(l < r)
{
int mid = l + r >> 1;
if(s.compare(sa[mid],T.size(),T) < 0) l = mid + 1;
else r = mid;
}
return s.compare(sa[l],T.size(),T) == 0;
}
void build_lcp(string& s)
{
n = s.size();
for(int i = 0;i <= n;++i) rank[sa[i]] = i;
int h = 0;
lcp[0] = 0;
for(int i = 0;i < n;++i)
{
int j = sa[rank[i] - 1];
if(h > 0) --h;
for(;j + h < n && i + h < n;++h)
if(s[j + h] != s[i + h])
break;
lcp[rank[i] - 1] = h;
}
}
}